# 计数排序
def countSort(arr):
    max_v = max(arr)
    min_v = min(arr)
    tmp_list = [0]*(max_v - min_v +1)
    for i in arr:
        tmp_list[i-min_v]+=1
    ret_list = []
    for i,v in enumerate(tmp_list):
        ret_list.extend([i+1]*v)
    return ret_list

if __name__ == '__main__':
    arr = [7, 2, 1, 5, 7, 8, 9]
    print(countSort(arr))
